package org.gc.amino.universe;

import java.util.ArrayList;
import java.util.List;

import org.gc.amino.ia.MoteSimulator;

public abstract class QuadTree implements CollidersFinder{
	public static final int BRANCHING_THRESHOLD = 4;
	public static final int QUADRANTS = 4;
	private Rectangle rect;
	private int max_depth;
	
	public static class Node extends QuadTree {
		private QuadTree[] quadrants;
		private int count;
		
		public Node(int max_depth, Rectangle rect) {
			super(max_depth, rect);
			
			this.quadrants = new QuadTree[4];
			for(int i = 0; i < QUADRANTS; ++i) {
				int depth           = super.getMaxDepth() - 1;
				Rectangle quad_rect = super.getRect().getQuadrant(i);
				this.quadrants[i] = new Leaf(depth, quad_rect);
			}
			this.count = 0;
		}
		
		/**
		 * 
		 * @param index Index of quadrant, between 0 and QuadTree.QUADRANTS - 1
		 * @return Corresponding QuadTree.
		 */
		public QuadTree getQuadrant(int index) {			
			return this.quadrants[index];
		}
		
		@SuppressWarnings("static-access")
		public QuadTree add(MoteSimulator mote) {
			this.count++;
			
			for(int i = 0; i < super.QUADRANTS; ++i) {
				QuadTree quad = this.getQuadrant(i);
				
				if(quad.intersects(mote)) {
					quad = quad.add(mote);
				}
			}
			
			return this;
		}
		
		public void addListToNode(List<MoteSimulator> mote_list) {
			for(MoteSimulator m : mote_list) {
				// Adding nodes won't cause further branching on this level
				this.add(m);
			}
		}
		
		@SuppressWarnings("static-access")
		public List<MoteSimulator> getPossibleColliders(MoteSimulator mote) {
			List<MoteSimulator> possible_colliders = new ArrayList<MoteSimulator>();
			
			for(int i = 0; i < super.QUADRANTS; ++i) {
				QuadTree quad = this.getQuadrant(i);
				if(quad.intersects(mote)) {
					possible_colliders.addAll(quad.getPossibleColliders(mote));
				}
			}
			
			return possible_colliders;
		}
		
		public void visit(Visitor visitor) {
			visitor.visitNode(this);
		}

		@Override
		public int getDepth() {
			int max = this.getQuadrant(0).getDepth();
			
			for(int i = 1; i < QUADRANTS; ++i) {
				int depth = this.getQuadrant(i).getDepth();
				if(depth > max) max = depth;
			}
			
			return max;
		}

		@Override
		public int getCount() {
			return this.count;
		}
	}
	
	public static class Leaf extends QuadTree {
		private List<MoteSimulator> mote_list;
		
		public Leaf(int max_depth, Rectangle rect) {
			super(max_depth, rect);
			this.mote_list = new ArrayList<MoteSimulator>();
		}
		
		@SuppressWarnings("static-access")
		public QuadTree add(MoteSimulator mote) {
			QuadTree quad = null;
			
			// if list size + 1 exceeds branching factor and max depth hasn't been reached
			if(super.getMaxDepth() > 0  && mote_list.size() >= super.BRANCHING_THRESHOLD - 1) {
				// creating a new node
				Node node = new Node(super.getMaxDepth() - 1, super.getRect());
				
				// adding the previous motes to it
				node.addListToNode(this.mote_list);
				// adding the mote
				node.add(mote);
				
				quad = node;
			}
			// else we'll simply add the mote to the list
			else {
				this.mote_list.add(mote);
				
				quad = this;
			}
			
			return quad;
		}
		
		public List<MoteSimulator> getPossibleColliders(MoteSimulator mote) {
			return this.mote_list;
		}

		public void visit(Visitor visitor) {
			visitor.visitLeaf(this);
		}

		@Override
		public int getDepth() {
			return 1;
		}

		@Override
		public int getCount() {
			return this.mote_list.size();
		}
	}
	
	public static class Root extends QuadTree {
		QuadTree quad;

		Root(int max_depth, Rectangle rect) {
			super(max_depth, rect);
			this.quad = new Leaf(max_depth, rect);
		}

		@Override
		public QuadTree add(MoteSimulator mote) {
			this.quad = this.quad.add(mote);
			return this;
		}

		@Override
		public List<MoteSimulator> getPossibleColliders(MoteSimulator mote) {
			return quad.getPossibleColliders(mote);
		}

		@Override
		public void visit(Visitor visitor) {
			this.quad.visit(visitor);			
		}

		@Override
		public int getDepth() {
			return this.quad.getDepth();
		}

		@Override
		public int getCount() {
			return this.quad.getCount();
		}
		
	}
	
 	public static abstract class Visitor {
		/**
		 * Visits a QuadTree vertically.
		 * @param quad
		 */
		public void visit(QuadTree quad) {
			this.visit(quad);
		}
		
		/**
		 * Visits a terminal quadrant.
		 * @param quad Terminal quadrant to visit
		 */
		protected abstract void visitLeaf(Leaf quad);
		
		/**
		 * Visits a non-terminal quadrant.
		 * @param quad Non-terminal quadrant to visit
		 */
		protected abstract void visitNode(Node quad);
		
	}

 	public static QuadTree newRoot(int max_depth, Rectangle rect) {
 		return new Root(max_depth, rect);
 	}
 	
	QuadTree(int max_depth, Rectangle rect) {
		this.max_depth = max_depth;		
		this.rect = rect;
	}
	
	
	public abstract QuadTree add(MoteSimulator mote);
	
	public QuadTree addList(List<MoteSimulator> list) {
		QuadTree quad = this; // handles the pathological situation where list is empty
		
		for(MoteSimulator mote : list) {
			quad = quad.add(mote);
		}
		
		return quad;
	}

	public abstract List<MoteSimulator> getPossibleColliders(MoteSimulator mote);
	
	public abstract void visit(Visitor visitor);

	public abstract int getDepth();
	
	public abstract int getCount();
	
	public Rectangle getRect() {
		return this.rect;
	}
	
	public int getMaxDepth() {
		return this.max_depth;
	}
	

	
	public boolean intersects(MoteSimulator mote) {
		return this.rect.intersects(mote.getRect());
	}
	
	public String toString() {
		return this.rect.toString();
	}
}
